<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<body>
<p>
  归并排序：

  算法复杂度 O(nlog(n)) <br>
  先分再合
</p>

<script>
  function mergeSort (arr) {
    if (arr.length <= 1) return arr

    const mid = arr.length / 2 | 0
    const left = mergeSort(arr.slice(0, mid))
    const right = mergeSort(arr.slice(mid))

    return merge(left, right)
  }

  function merge (left, right) {
    let i = 0
    let j = 0
    const rst = []
    while (i < left.length && j < right.length) {
      rst.push(left[i] < right[j] ? left[i++] : right[j++])
    }
    return rst.concat(i < left.length ? left.slice(i) : right.slice(j))
  }

  console.log(mergeSort([9, 5, 3, 4, 100, 2, 1]))
</script>
</body>
</html>
